#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1e5+7,inf=1e12;
ll n,Q,a[Maxn],lfm[Maxn],rfm[Maxn],k,answer[Maxn][2];
ll stk[Maxn],top,ans;
int main(){
	freopen("summer.in","r",stdin);
	freopen("summer.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	a[0]=a[n+1]=inf;
	scanf("%lld",&Q);
	if(n<=1000&&Q<=1000){
		while(Q--){
			ll x,l,r;
			scanf("%lld%lld%lld",&x,&l,&r);
			swap(a[x],a[x+1]);
			
			for(ll i=1;i<=n;i++){
				while(top&&a[stk[top]]<=a[i]) --top;
				lfm[i]=stk[top];
				stk[++top]=i;
			}top=0;
			for(ll i=n;i;i--){
				while(top&&a[stk[top]]<=a[i]) --top;
				rfm[i]=stk[top];
				if(top==0) rfm[i]=n+1;
				stk[++top]=i;
			}top=0;
			ans=0;
			ll res=0;
			for(ll t=l;t<=r;t++){
				ll pts=a[t];
				ll L=t,R=t;
				res=0;
				while(true){
					R=rfm[R];
					res++;
					while(a[L]<a[R]) L=lfm[L],res++;
					if(a[L]==a[R]) res--;
					if(R==n+1&&L==0) break;
				}
				res--;
				ans+=res*k;
			}
			
			cout<<ans+(n-1)*(r-l+1)<<endl;
		}
	}
	for(ll i=1;i<=n;i++){
		while(top&&a[stk[top]]<=a[i]) --top;
		lfm[i]=stk[top];
		stk[++top]=i;
	}top=0;
	for(ll i=n;i;i--){
		while(top&&a[stk[top]]<=a[i]) --top;
		rfm[i]=stk[top];
		if(top==0) rfm[i]=n+1;
		stk[++top]=i;
	}top=0;
	ans=0;
	ll res=0;
	for(ll t=1;t<=n;t++){
		ll pts=a[t];
		ll L=t,R=t;
		res=0;
		while(true){
			R=rfm[R];
			res++;
			while(a[L]<a[R]) L=lfm[L],res++;
			if(a[L]==a[R]) res--;
			if(R==n+1&&L==0) break;
		}
		res--;
		answer[t][0]+=res*k;
	}
	swap(a[1],a[2]);
	for(ll i=1;i<=n;i++){
		while(top&&a[stk[top]]<=a[i]) --top;
		lfm[i]=stk[top];
		stk[++top]=i;
	}top=0;
	for(ll i=n;i;i--){
		while(top&&a[stk[top]]<=a[i]) --top;
		rfm[i]=stk[top];
		if(top==0) rfm[i]=n+1;
		stk[++top]=i;
	}top=0;
	for(ll t=1;t<=n;t++){
		ll pts=a[t];
		ll L=t,R=t;
		res=0;
		while(true){
			R=rfm[R];
			res++;
			while(a[L]<a[R]) L=lfm[L],res++;
			if(a[L]==a[R]) res--;
			if(R==n+1&&L==0) break;
		}
		res--;
		answer[t][1]+=res*k;
	}
	for(ll i=1;i<=n;i++) answer[i][0]+=answer[i-1][0],answer[i][1]+=answer[i-1][1];
	for(ll i=1;i<=Q;i++){
		ll l,r,x;
		cin>>x>>l>>r;
		cout<<answer[r][i&1]-answer[l-1][i&1]+(r-l+1)*(n-1)<<endl;
	}
	return 0;
}
/*
7 7
4 3 2 1 2 3 4
5
1 1 3
1 3 5
1 2 5
1 1 5
1 1 5

39
67
73
86
86

*/
